//
//  Problem1029.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/21.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1029. 两地调度
 公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0]，飞往 B 市的费用为 costs[i][1]。
 返回将每个人都飞到某座城市的最低费用，要求每个城市都有 N 人抵达。

 示例：
     输入：[[10,20],[30,200],[400,50],[30,20]]
     输出：110
     解释：
     第一个人去 A 市，费用为 10。
     第二个人去 A 市，费用为 30。
     第三个人去 B 市，费用为 50。
     第四个人去 B 市，费用为 20。

    最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。

 提示：
     1 <= costs.length <= 100
     costs.length 为偶数
     1 <= costs[i][0], costs[i][1] <= 1000
 */
@objcMembers class Problem1029: NSObject {
    func solution() {
        print(twoCitySchedCost([[10,20],[30,200],[400,50],[30,20]]))
    }
    
    /*
     排序：
     假设所有人都去B市，那么去B的费用就是所有的cost[1]的和=sumB，去A的费用就是sumA=0, 总费用 all = sumB + sumA => sumB + 0
     我们需要拿N个人去A市，假如让i去A，那么B的sumB -= costs[i][1], sumA += costs[i][0], 总费用 all = sumB + sumA => sumB + cost[i][0] - cost[i][1], 把后面的合并：all = sumB + (costs[i][0]-costs[i][1]), 让all最小，那么就让(costs[i][0]-costs[i][1])最小
     我们按照(costs[i][0]-costs[i][1])进行排序，前N个去A市，后N个去B市
     
     */
    func twoCitySchedCost(_ costs: [[Int]]) -> Int {
        let list = costs.sorted { f, s in
            return (f[0]-f[1]) < (s[0]-s[1])
        }
        var sum = 0
        for i in 0..<costs.count/2 {
            sum += list[i][0] + list[costs.count/2 + i][1]
        }
        return sum
    }
}
